package 二叉树;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class _94_二叉树的中序遍历 {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new LinkedList<>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		while (!stack.isEmpty() || node != null) {
			if (node != null) {
				stack.push(node);
				node = node.left;
			} else {
				node = stack.pop();
				list.add(node.val);
				node = node.right;
			}
		}
		return list;
	}

}
